(Monero) The Bug in CryptoNote protocol (2017)
CryptoNoteは、Moneroでベースになっているプロトコル。
暗号学的なトリックを用いることで、二重支払いが可能になる脆弱性で、Moneroではバグをfixした後に発表した。ByteCoinでは700 million coinが攻撃者によって生成された。
Disclosure of a Major Bug in CryptoNote Based Currencies
Moneroの秘匿送金は主に3つのパートから成る。
Amountの秘匿化：Bullet Proof （以前はRingCT）
Pedersen Commitmentによる送金額の秘匿化 & Range Proof（Bullet Proof)による送金額Rangeの証明
Receiverの秘匿化：Stealth Address
DH鍵交換をベースに送り手と受け手しか知らないStealthアドレスに送金し、かつそのアドレスの秘密鍵は受け手しか知らない。
Dual-Key Stealth Address Protocolによりviewing keyのシェアを可能に。
Senderの秘匿化：リング署名
消費するUTXOと同じ量のTXO（UnspentでもSpentでもOK）をブロックチェーンからランダムに複数選択し、インプットにセットする。
.$ TXO_a, TXO_b, TXO_c, TXO_d, ... => $ RingSignature｜Pubkey_a, PubKey_b, PubKey_c, PubKey_d,...
リング署名によりいずれかの公開鍵に対応する秘密鍵で署名されたことは分かるが、実際にどのTXOが使われたかは分からない。
https://gyazo.com/079bf317dc1337de1af00c0a693c1654
これにより秘匿性が得られる反面、どのUTXOが消費されたか他の人から分からないためUTXOの二重支払いが可能になってしまう。
これを防ぐために、実際に消費するUTXOに紐づく秘密鍵から決定論的なキーイメージ$ Iをトランザクションインプットに加える。
,$ I = x * groupHash(P) (I：キーイメージ、秘密鍵：x、P：公開鍵）
キーイメージがこれまで存在していないかチェックすることでUTXOの二重支払いを防ぐ。
このキーイメージを攻撃者が意図的に変更し、二重支払いを可能にする脆弱性が存在した。
Cofactor
具体的なcurve達
安全性と演算効率性のトレードオフで、Cofactorが1以外だと実装上セキュリティ的に気をつけないといけないことが増えるけど、演算の効率性はprime orderより良いので、cofactorが1以外（4とか8）の曲線が多く使われるようになってきている。が、現状cofactor=1のsecp256k1が多い。
ブロックチェーン文脈ではざっくり分けて、
secp256k1 (有限体位数が256-bit prime）: bitcoin, ethereum, grin, tron, zilliqa, tendermint, EOS
k: Koblitz
$ y^2 = x^3 + ax + bでa=0, b=7で固定
secp256r1と比べて数bit程度セキュリティが弱い分、演算は効率的。
secp256r1: ontology, EOS
r: random
aとbがランダム。（であると言われている）
curve25519（montgomery curve）：monero, substrate
EdDSAで使われるed25519（twisted edwards curve）が有名
Things that use Curve25519
ペアリングが得意な曲線: cofactor = 8が多い
zcash (jubjub(Bls12-381)), dfinity（Bls12-381）, ethereum pre-compile(Alt-BN256), ethereum beaconchain(Bls12-381)
群論的な話
群：いろいろ公理あるけどざっくりと「足し算とかの演算ができる集合」
（楕円曲線の）群の位数 (group order)：群の元の数
（部分群(subgroup)の）元の位数(point of order)：群のある元を生成元として有限部分巡回群（非自明な部分群）が作れるとき、その部分巡回群の位数。
例えば、
.$ E/F_{13}: y^2 = x^3 + 4に有理点の数が21
位数3の点がP1, P2の2つ(無限遠点Oを加えて3つの元が部分群)
元を3倍するとOに。
shuntak.icon < 位数3の巡回群なので3倍するとOになる
位数7の点がP11, P12, P13, P14, P17, P18 の6つ(無限遠点Oを加えて7つの元が部分群）
元を3倍しても位数7の点。
shuntak.icon < 位数7の巡回群なので3倍してもOにならない
位数21の点がP3, P4, P5, P6, P7, P8, P9, P10, P15, P16, P19, P20 の12個
元を3倍すると位数7の点に。
群論でのラグランジェの定理：群Gの部分群の位数は、Gの位数の約数になる。
例えば、#E(F_q) = 105 = 3*5*7の場合、群の位数(とsubgroup)は{1, 3, 5, 7, 15, 21, 35, 105}のいずれかになる。
cofactor = (群の位数）/ (元の位数）
secp256k1: 1
curve25519: 8
Cofactorが8であるということは、prime orderであるsubgroupの位数が群の位数の1/8であるということで、cofactorを$ h、prime orderを$ lとして群の位数は$ h\cdot lと表現される。
つまり、群の位数が素数じゃない時にcofactorが存在してしまい、ECDLPはそのsubgroupの素数位数に依存してしまう。
例えば、群の位数が966 = 2 * 3 * 7 * 23の時、位数23のsubgroupのECDLPに安全性仮定が移ってしまう。
中国剰余定理により最大のprime subgroup orderのECDLPが群のECDLPを解くことの計算ボトルネックになっている。
素数位数群以外の点(low order point)は極端に位数が小さく暗号のために使い物にならないので、cofactorを持つ楕円曲線で暗号を実装する時は、確かにその点が素数位数群上にあることを保証する必要がある。
群の元にその位数をかけると無限遠点にKILLされるので、素数位数をかけて無限遠点になれば確かに素数位数群上の点であることが検証できる。
逆に、cofactor 8を点に乗算するとlow order pointの場合は無限遠点になる。
具体的なコード
素数位数を乗算してKILLされることをチェックしてから素数位数Subgroup上の点インスタンスを生成している。
code:subgroup.rs
/// Attempts to cast this as a prime order element, failing if it's
/// not in the prime order subgroup.
pub fn as_prime_order(&self, params: &E::Params) -> Option<Point<E, PrimeOrder>> {
if self.mul(E::Fs::char(), params) == Point::zero() {
Some(convert_subgroup(self))
} else {
None
}
}
Moneroでも、キーイメージ生成時のこのような基本的なsmall subgroup attack対策はされていて、$ I = x * groupHash(P)を生成する時に、groupHashでoutputに8を乗算して素数位数の群にあることを保証している。
↓ jubjub curve
code:subgroup.rs
/// Produces a random point in the Jubjub curve.
/// The point is guaranteed to be prime order
/// and not the identity.
pub fn group_hash<E: JubjubEngine>(
params: &E::Params
) -> Option<edwards::Point<E, PrimeOrder>>
{
assert_eq!(personalization.len(), 8);
// Check to see that scalar field is 255 bits
assert!(E::Fr::NUM_BITS == 255);
let mut h = Blake2s::with_params(32, &[], &[], personalization);
h.update(constants::GH_FIRST_BLOCK);
h.update(tag);
let h = h.finalize().as_ref().to_vec();
assert!(h.len() == 32);
match edwards::Point::<E, _>::read(&mut &h.., params) { Ok(p) => {
let p = p.mul_by_cofactor(params); // バイト列から曲線上に乗っけた点にさらにcofactor(=8)を乗算
if p != edwards::Point::zero() { // cofactorを乗算した結果の点が無限遠点でなければ、
Some(p) // 素数位数群の上の点であることが保証されている。
} else {
None // 無限遠点であれば、low order pointであり使えない。
}
},
Err(_) => None
}
}
SNARK内でも公開鍵がsmall orderではないかチェック。
code:subgroup.rs
// Ensure ak is large order.
ak.assert_not_small_order(
cs.namespace(|| "ak not small order"),
self.params
)?;
Moneroで起きた脆弱性
UTXOに紐づく秘密鍵から決定論的に計算されるキーイメージが存在しないことがUTXOを消費できる条件。つまり、$ Iに対する署名検証を通れれるような別の$ I'を作ることができれば二重支払いができる。
https://gyazo.com/12ed11a88952e895d1c34a1534cf3404
簡単のためRing size = 1 で考えると、
,$ I = x * groupHash(P) (I：キーイメージ、秘密鍵：x、P：公開鍵）
.$ e = hash(m, kG, k*groupHash(P)) (m: メッセージ、 k: ランダムスカラー）
.$ s = k - e*x
よって署名は$ (I, e, s)
署名検証は、
$ e == hash(m, sG + eP, s*groupHash(P) + eI)
署名検証においてキーイメージは$ e*Iで評価される。
.$ e:ランダム値
つまり、$ eI' = eIとなるような別のキーイメージ$ I'を作れれば二重支払いができる。
$ Lをlow order point上の点（つまり、その位数$ oはせいぜい8)として、攻撃キーイメージを$ I' = I + Lとする。
もしランダムな値$ eが$ oで割り切れるとすると、$ e = e' * oとなり、署名検証での攻撃キーイメージは、$ e * I' = e * I + (e' * o) * L = e * I（$ Lにその位数$ oを乗算しているので無限遠点になる。）
ここで$ oはせいぜい8なので、ランダムな$ eが$ oで割り切れるまで繰り返し行えば良い。
以上のような、curve22519がcofactor=8を持つことが原因で起きた脆弱性に対し、Moneroでの解決策は、ブロックチェーンに送られたキーイメージが素数群上にあるかの検証を加えること。
具体的には、キーイメージ$ Iが素数位数$ lでKILLされるか（$ l*I=Oか）チェックを加える。
（low order pointを加算した点は素数位数群ではなくなるん？）
moonty_sal.icon < 確かにこれどういう対策なんだろう。
$ lは一般的に大きな素数なのでこの追加検証コストはけっこうでかいはず。
Fixしているプルリク
修正箇所
code:fix.cpp
bool core::check_tx_inputs_keyimages_domain(const transaction& tx) const
{
std::unordered_set<crypto::key_image> ki;
for(const auto& in: tx.vin)
{
CHECKED_GET_SPECIFIC_VARIANT(in, const txin_to_key, tokey_in, false);
if (!(rct::scalarmultKey(rct::ki2rct(tokey_in.k_image), rct::curveOrder()) == rct::identity()))
return false;
}
return true;
}
ちなみに、攻撃キーイメージに加えるlow order pointの$ Lをゲットするシンプルな方法は、群の位数$ h*lのGenerator pointに対し、low orderのcofactor = $ (h*l) / a where a = {2, 4, 8} を乗算すると得られる。
ちなみに、以上のようなcurve25519のCofactorによる脆弱性を防ぐために開発されたのがDecaf protocolをcofactor 8用に応用したRisrettoで、curve25519をcofactor=1であるように実装できるレイヤーを提供する。substrateでもデフォルトで導入予定。 Refs
Disclosure of a Major Bug in CryptoNote Based Currencies
(curves) CryptoNote and equivalent points
CryptoNote v 2.0
Exploiting Low Order Generators in One-Time Ring Signatures
2017年に起きたMoneroのキーイメージを細工したコイン無限生成の脆弱性の内容
How does the recent patched key image exploit work in practice?